
import java.util.ArrayList;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */


//import Excepciones.*;
/**
 *
 * @author guillem.caceres
 */
public class Trie
{

    private Trie hijo;
    private Trie hermano;
    private Nodo nodo;
    private int altura;
    private int palabras;


    /**
     * Constructor de Tries. Cada trie tiene un nodo de tipo Nodo, un puntero al hijo y otro al hermano, y
     * la altura del trie.
     * @param nodo - Nodo
     */
    public Trie (Nodo nodo) {
        this.nodo = nodo;
        this.hijo = null;
        this.hermano = null;
        this.altura = 0;
        this.palabras = 0;
    }


    /**
     * Devuelve el nodo de la posicion actual del trie.
     * @return this.nodo - Nodo
     */
    public Nodo GetNodo()
    {
        return this.nodo;
    }

 /**
     * Devuelve el caracter de la posicion actual del trie.
     * @return caracter - Char
     */
    public char GetChar() {
        return nodo.GetCaracter();
    }

    public boolean EsFinPalabra () {
        return nodo.EsFinPalabra();
    }

    /**
     * Devuelve la altura del trie.
     * @return this.altura - int
     */
    public int GetAltura()
    {
        return this.altura;
    }


    /**
     * Devuelve el siguiente hermano del nodo.
     * @return this.hermano - Trie
     */
    public Trie GetSiguienteHermano()
    {
        return this.hermano;
    }


    /**
     * Devuelve el siguiente hijo del nodo.
     * @return
     */
    public Trie GetSiguienteHijo()
    {
        return this.hijo;
    }

    public int GetPalabras () {
        return this.palabras;
    }

    /**
     * Calcula la altura del trie recorriendolo entero y escogiendo siempre el camino mas largo.
     * @return altura - int
     */
    public int CalcularAltura() {
        if (this != null){
            if (hijo != null && hermano != null){
                return Math.max(1+hijo.CalcularAltura(),hermano.CalcularAltura());
            }
            else if(hijo != null) {
                return (1+hijo.CalcularAltura());
            }
            else if(hermano != null) {
                return (hermano.CalcularAltura());
            }
            else return 0;
        }
        return 0;
    }


    /**
     * Devuelve si la palabra a sido insertada o no. En caso de que la palabra ya exista en el trie no se inserta.
     * Una vez insertada, si esta palabra es la mas grande del trie se actualiza la altura del trie.
     * @param palabra - String
     * @return estado -boolean
     */
    public boolean insertarPalabra(String palabra) {
        if (EstaEnTrie(palabra,0)) return false;
        ++palabras;
        insertar(palabra);
        if (altura < palabra.length()) altura = palabra.length();
        return true;
    }


    /**
     * Inserta la palabra en el trie de diccionario. Se recorre el trie comparando caracter con caracter con la
     * palabra que se nos da.
     * @param palabra - String
     */
    private void insertar(String palabra) {
        if (palabra.length() >= 1) { // Mientras el string no este vacio
            char pos = palabra.charAt(0); // Cojemos el primer caracter de la palabra
            if (nodo.GetCaracter() == 0 || nodo.GetCaracter() == pos) {
                if (nodo.GetCaracter() == 0) nodo.SetCaracter(pos);
                if (hijo == null){
                    Trie aux = new Trie(new Nodo());
                    hijo = aux;
                }
                hijo.insertar(palabra.substring(1));
            }
            else if (nodo.GetCaracter() < pos) {
                if (hermano == null) {
                    Trie aux = new Trie(new Nodo());
                    hermano = aux;
                }
                hermano.insertar(palabra);
            }
            else {
                Trie aux2 = new Trie(new Nodo());
                aux2.hijo = hijo;
                aux2.hermano = hermano;
                aux2.nodo.SetCaracter(nodo.GetCaracter());
                Trie aux = new Trie(new Nodo());
                aux.nodo.SetZero();
                hijo = aux;
                hermano = aux2;
                nodo.SetCaracter(pos);
                hijo.insertar(palabra.substring(1));

            }
        }
        else if (nodo.GetCaracter() != 0) {
            if (hermano == null){
                Trie aux = new Trie(new Nodo());
                hermano = aux;
            }
            hermano.insertar(palabra);
        }
        else nodo.SetFinal();
    }


    /**
     * Se inserta una regla en el trie de reglas. Primero se recorre el trie de alpha, si la palabra no existia
     * se inserta y conseguimos el nuevo trie de beta de esa palabra, y si la palabra ya existia se recorre y se
     * consigue el trie de beta. Comprovamos si es necesario actualizar la altura del trie.
     * Insertamos si beta en el trie de beta en caso de que no exista i conseguimos el contador de accesos de esa regla.
     * Si la palabra existia se incrementa el contador en uno.
     * @param alpha - String
     * @param beta - String
     * @return estado - boolean
     */
    public void insertarRegla(String alpha, String beta, int cont) {
        Trie aux = insertar2(alpha);
        if (altura < alpha.length()) altura = alpha.length();
        //System.out.println(aux.nodo.GetCaracter());
        if (aux == null) aux = new Trie(new Nodo());
        int n = aux.insertar3(beta, cont);
        if (aux.altura < beta.length()) aux.altura = beta.length();
    }


    /**
     * Devuelve el trie del ultimo nodo del trie de alphas. Si la palabra no existia en el trie se inserta y se crea
     * el nuevo trie que se devuelve, mientras que si ya existia se recorre el trie hasta llegar al trie del ultimo nodo
     * y se devuelve este.
     * @param palabra - String
     * @return t - Trie
     */
    private Trie insertar2(String palabra) {
        if (palabra.length() >= 1) { // Mientras el string no este vacio
           // System.out.println(palabra.length());
            char pos = palabra.charAt(0); // Cojemos el primer caracter de la palabra
            //System.out.println("pos = ");
            //System.out.println(pos);
            if (nodo.GetCaracter() == 0 || nodo.GetCaracter() == pos) {
                if (nodo.GetCaracter() == 0) nodo.SetCaracter(pos);
                if(hijo == null)
                {
                    if (palabra.length() == 1){
                        //System.out.println("comprobar");
                        Trie aux2 = new Trie(new Nodo());
                        Trie aux = new Trie(new Nodo(aux2));
                        hijo = aux;
                    }
                    else {
                        Trie aux = new Trie(new Nodo());
                        hijo = aux;
                    }
                }
                else if (hijo.nodo.EsFinPalabra() && palabra.length() > 1) {
                    //System.out.println("HE ENTRADO");
                    Trie aux2 = new Trie(new Nodo());
                    aux2.hermano = hijo;
                    hijo = aux2;
                }
                /*else if (palabra.length() == 1){
                   hijo.FinPalabra();
                   return hijo.GetUltimoNodoAlpha(palabra);
                }*/
              //  System.out.println(nodo.GetCaracter());
                return hijo.insertar2(palabra.substring(1));
            }
            else if (nodo.GetCaracter() < pos) {
                if (hermano == null) {
                    if (palabra.length() == 1){
                        Trie aux2 = new Trie(new Nodo());
                        Trie aux = new Trie(new Nodo(aux2));
                        hermano = aux;
                    }
                    else {
                        Trie aux = new Trie(new Nodo());
                        hermano = aux;
                    }
                }
                return hermano.insertar2(palabra);
            }
            else {
                Trie aux2;
                if (nodo.EsFinPalabra()) {
                    Trie aux3 = new Trie(new Nodo());
                    aux2 = new Trie(new Nodo(aux3));
                    aux2.nodo.SetFinal();
                }
                else aux2 = new Trie(new Nodo());
                aux2.hijo = hijo;
                aux2.hermano = hermano;
                nodo.copiarNodo(aux2.nodo); //funcio per corregir l'error
                Trie aux;
                if (palabra.length() == 1) {
                    Trie aux4 = new Trie(new Nodo());
                    aux = new Trie(new Nodo(aux4));
                }
                else aux = new Trie(new Nodo());
                aux.nodo.SetZero();
                hijo = aux;
                hermano = aux2;
                nodo.SetCaracter(pos); //lloc on es borrava la regla
                return hijo.insertar2(palabra.substring(1));
            }
        }
        else if (nodo.EsFinPalabra()){
            return nodo.GetTrieBeta();
        }
        else if (nodo.GetCaracter() != 0) {
           // System.out.println("xibato_aux");
            if (hermano == null){
                Trie aux2 = new Trie(new Nodo());
                Trie aux = new Trie(new Nodo(aux2));
                hermano = aux;
            }
            return hermano.insertar2(palabra);
        }
        else {
            nodo.SetFinal();
            return nodo.GetTrieBeta();
            }
    }


    private void FinPalabra () {
        nodo.SetFinal();
    }


    /**
     * Se devuelve el contador de accesos a la regla beta que se nos pasa. Si la palabra beta no existia
     * se inserta en el trie y el contador de accesos pasa a ser uno. Si ya existia se recorre el trie y
     * se incrementa en uno el contador.
     * @param palabra - String
     * @return prob - int
     */
    private int insertar3(String palabra, int cont) {
        if (palabra.length() >= 1) { // Mientras el string no este vacio
          //  System.out.println(palabra.length());
            char pos = palabra.charAt(0); // Cojemos el primer caracter de la palabra
            if (nodo.GetCaracter() == 0 || nodo.GetCaracter() == pos) {
                if (nodo.GetCaracter() == 0) nodo.SetCaracter(pos);
                if (hijo == null){
                    if (palabra.length() == 1){
                        Trie aux2 = new Trie(new Nodo());
                        Trie aux = new Trie(new Nodo(aux2));
                        hijo = aux;
                    }
                    else {
                        Trie aux = new Trie(new Nodo());
                        hijo = aux;
                    }
                }
                else if (hijo.nodo.EsFinPalabra() && palabra.length() > 1) {
                    Trie aux2 = new Trie(new Nodo());
                    aux2.hermano = hijo;
                    hijo = aux2;
                }
                //System.out.println(nodo.GetCaracter());
                return hijo.insertar3(palabra.substring(1), cont);
            }
            else if (nodo.GetCaracter() < pos) {
                if (hermano == null) {
                    if (palabra.length() == 1){
                        Trie aux2 = new Trie(new Nodo());
                        Trie aux = new Trie(new Nodo(aux2));
                        hermano = aux;
                    }
                    else {
                        Trie aux = new Trie(new Nodo());
                        hermano = aux;
                    }
                }
                else if (hermano.nodo.GetCaracter() > pos) {
                    Trie aux = new Trie(new Nodo());
                    aux.hermano = hermano;
                    hermano = aux;
                }
                return hermano.insertar3(palabra, cont);
            }
            else {
                Trie aux2;
                if (nodo.EsFinPalabra()) {
                    Trie aux3 = new Trie(new Nodo());
                    aux2 = new Trie(new Nodo(aux3));
                }
                else aux2 = new Trie(new Nodo());
                aux2.hijo = hijo;
                aux2.hermano = hermano;
                aux2.nodo.SetCaracter(nodo.GetCaracter());
                Trie aux;
                if (palabra.length() == 1) {
                    Trie aux4 = new Trie(new Nodo());
                    aux = new Trie(new Nodo(aux4));
                }
                else aux = new Trie(new Nodo());
                aux.nodo.SetZero();
                hijo = aux;
                hermano = aux2;
                nodo.SetCaracter(pos);
                return hijo.insertar3(palabra.substring(1), cont);
            }
        }
        else if (nodo.EsFinPalabra()){
            nodo.IncProb(cont);
            return nodo.GetProb();
        }
        else if (nodo.GetCaracter() != 0) {
            if (hermano == null){
                Trie aux2 = new Trie(new Nodo());
                Trie aux = new Trie(new Nodo(aux2));
                hermano = aux;

            }
            return hermano.insertar3(palabra, cont);
        }
        else {
            nodo.SetFinal();
            nodo.IncProb(cont);
            return nodo.GetProb();
            }
}


    /**
     * Devuelve el trie del ultimo nodo del trie alpha.
     * @param alpha - String
     * @return t - Trie
     */
    public Trie GetUltimoNodoAlpha(String alpha){
        if (alpha.length() >= 1) { // Mientras el string no este vacio
            char pos = alpha.charAt(0); // Cojemos el primer caracter de la palabra
            if (nodo.GetCaracter() < pos) { // Si el caracter es mas pequeño que el que buscamos
                return hermano.GetUltimoNodoAlpha(alpha);
            }
            else return hijo.GetUltimoNodoAlpha(alpha.substring(1));
        }
        else if(nodo.EsFinPalabra()) return nodo.GetTrieBeta();
        else return hermano.GetUltimoNodoAlpha(alpha);
    }


    /**
     * Devuelve el contador de accesos del ultimo nodo del trie Beta
     * @param beta - String
     * @return prob - int
     */
    public int GetUltimoNodoBeta(String beta){
        if (beta.length() >= 1) { // Mientras el string no este vacio
            char pos = beta.charAt(0); // Cojemos el primer caracter de la palabra
            if (nodo.GetCaracter() < pos) { // Si el caracter es mas pequeño que el que buscamos
                return hermano.GetUltimoNodoBeta(beta);
            }
            else return hijo.GetUltimoNodoBeta(beta.substring(1));
        }
        else if(nodo.EsFinPalabra()) return nodo.GetProb();
        else {
            return hermano.GetUltimoNodoBeta(beta);
        }
    }


    /**
     * Devuelve si la palabra ha estado eliminada o no. Se comprueba si la palabra existe en el trie, si no existe
     * no se hace la eliminacion, pero si existe la palabra es eliminada, y si era una de las palabras mas largas del trie
     * se recalcula la altura del trie.
     * @param palabra - String
     * @return estado - boolean
     */
    public boolean eliminarPalabra(String palabra) {
        if (!EstaEnTrie(palabra,0)) return false;
        eliminar(palabra);
        if (palabra.length() == altura) {
            altura = 0;
            altura = CalcularAltura();
        }
        return true;
    }



    /**
     * Elimina la palabradel trie. Recorre toda la palabra y una vez llegado al ultimo caracter se van eliminando
     * todos los nodos del trie que solo usavan esa palabra.
     * @param palabra - String
     * @return estado - boolean
     */
    private boolean eliminar(String palabra) {
        if(palabra.length() >= 1) { // Mientras el string no este vacio
            char pos = palabra.charAt(0); // Cojemos el primer caracter de la palabra
            if(nodo.GetCaracter() < pos) { // Si el caracter es menor al que queremos eliminar
                if (hermano.eliminar(palabra)) { // Si se tiene que eliminar el hijo derecho
                    if (hermano.hermano == null) {
                        hermano = null;
                    }
                    else {
                        Trie aux = hermano.hermano;
                        hermano.nodo.SetZero();
                        hermano.hermano = null;
                        hermano = aux;
                    }
                }
                return false;
            }
            else if (nodo.GetCaracter() == pos) { // Si es el caracter que queremos eliminar
                if (hijo.eliminar(palabra.substring(1))) {
                    if (hijo.hermano == null) { // Si el hijo izquierdo no tiene hijo derecho
                        hijo = null;
                        nodo.SetZero();
                        if (hermano != null){
                            Trie aux = hermano;
                            hermano = aux.hermano;
                            hijo = aux.hijo;
                            nodo.SetCaracter(aux.nodo.GetCaracter());
                            return false;
                        }
                        return true;
                    }
                    else { // Si hijo izquierdo tiene hijo derecho hay que elminar el primero y colocar bien el trie
                        Trie aux = hijo.hermano;
                        hijo.nodo.SetZero();
                        hijo.hermano = null;
                        hijo = aux;
                        return false;
                    }
                }
                return false;
            }
        }
        else if(!nodo.EsFinPalabra()) { // Si no encontramos el final de palabra avanzamos por hijo derecho
            hermano.eliminar(palabra);
            if (hermano.nodo.GetCaracter() == 0) hermano = null;
            return false;
        }
        else nodo.SetZero();
        return true;
    }


    /**
     * Devuelve la primera palabra del trie. Si el trie es vacio se lanza una excepcion.
     * @return palabra - String
     * @throws ExcepcionVacio
     */
    public String PrimeraPalabra() {//throws ExcepcionVacio {
        //if (TrieVacio()) throw new ExcepcionVacio("El diccionario esta vacio");
        StringBuilder cadena = new StringBuilder(); // Cadena que cambia de tamaño
        return PrimeraPalabraTrie(cadena);
    }


    /**
     * Devuelve la primera palabra del trie.
     * @param cadena - StringBuilder
     * @return palabra - String
     */
    private String PrimeraPalabraTrie(StringBuilder cadena) {
        if (!nodo.EsFinPalabra()) { // Mientras no encontremos el final de la primera palabra
            cadena.append(nodo.GetCaracter());
            return hijo.PrimeraPalabraTrie(cadena);
        }
        return cadena.toString(); // copiamos la palabra a un string normal para retronarlo
    }

    /**
     * Avanza los dos tries hasta que llega al final el primer trie. Necesario para la funcion buscar palabras.
     * @param principal - principal
     */
    public void CopiarTrie(Trie principal){
        if (!hijo.nodo.EsFinPalabra()) {
            if (principal.nodo.GetCaracter() < nodo.GetCaracter()) CopiarTrie(principal.hermano);
            else if(nodo.GetCaracter() == principal.nodo.GetCaracter())  hijo.CopiarTrie(principal.hijo);
        }
        else {
            if (principal.nodo.GetCaracter() < nodo.GetCaracter()) CopiarTrie(principal.hermano);
            else hijo = principal.hijo;
        }
    }


    /**
     * Indica si el trie esta vacio o no.
     * @return estado - boolean
     */
    public boolean TrieVacio() {
        if (hijo == null && hermano == null) return true;
        return false;
    }


    /**
     * Indica si la palabra existe en el trie o no. Si el trie esta vacio lanza una excepcion
     * @param palabra - String
     * @return estado - boolean
     * @throws ExcepcionVacio
     */
    public boolean Existe(String palabra) {//throws ExcepcionVacio {
        //if (TrieVacio()) throw new ExcepcionVacio("El diccionario esta vacio");
        return EstaEnTrie(palabra,0);
    }

    public boolean ExisteBeta(String alpha, String beta) {//throws ExcepcionVacio {
        //if (TrieVacio()) throw new ExcepcionVacio("El diccionario esta vacio");
        return GetUltimoNodoAlpha(alpha).EstaEnTrie(beta, 1);
    }

    public boolean ExisteBeta2(Trie t, String beta) {//throws ExcepcionVacio {
        //if (TrieVacio()) throw new ExcepcionVacio("El diccionario esta vacio");
        return t.EstaEnTrie(beta, 1);
    }


    /*
     * Indica si la palabra existe o no en el trie. En mode 0 tiene en cuanta el nodo de final de palabra, mientras
     * que en mode 1 no, necesario para el caso Buscar palabras.
     */
    private boolean EstaEnTrie(String palabra, int mode) {
        if (palabra.length() >= 1) { // Mientras el string no este vacio
            char pos = palabra.charAt(0); // Cojemos el primer caracter de la palabra
            if (nodo.GetCaracter() < pos) { // Si el caracter es mas pequeño que el que buscamos
                if (hermano == null) return false;
                return hermano.EstaEnTrie(palabra, mode);
            }
            else if (nodo.GetCaracter() == pos) return hijo.EstaEnTrie(palabra.substring(1), mode);
            else return false;
        }
        if (nodo.EsFinPalabra() || mode == 1) return true;
        else {
            if (hermano == null) return false;
            return hermano.EstaEnTrie(palabra, mode);
        }
    }


    /**
     * Devuelve un trie con las palabras pertenecientes al trie que contienen como prefijo el patron.
     * @param patron - String
     * @return resultat - Trie
     * @throws ExcepcionVacio
     */
    public Trie BuscarPalabras(String patron) {//throws ExcepcionVacio {
        Trie resultat  = new Trie(new Nodo());
        if (EstaEnTrie(patron,1) && !TrieVacio()) { // Si existe alguna palabra que empieze por el patron
            resultat.insertar(patron); // Se inserta el patron al trie vacio
            Trie principal = new Trie(new Nodo());
            principal.hijo = hijo;
            principal.hermano = hermano;
            principal.nodo = nodo;
            principal.nodo.SetCaracter(nodo.GetCaracter());
            resultat.CopiarTrie(principal); // Se insertaran las otras palabras que siguen el patron
        } // Si no existe ninguna palabra que empieze por el patron se devuelve un trie vacio
        return resultat;
    }
   
    
    public void getPalabrasAlpha(ArrayList<String> cadenas) {
        StringBuilder cadena = new StringBuilder();
        getPalabrasAlpha(cadenas,cadena);
    }
    
    private void getPalabrasAlpha(ArrayList<String> cadenas, StringBuilder cadena){
        if (nodo.EsFinPalabra()) cadenas.add(cadena.substring(0));
        else {
            if(hijo != null) {
                cadena.append(nodo.GetCaracter());
                hijo.getPalabrasAlpha(cadenas,cadena);
            }
            if ((cadena.length()-1) >= 0) cadena.deleteCharAt(cadena.length()-1);
            if (hermano != null) {
                hermano.getPalabrasAlpha(cadenas,cadena);
            }
        }
    }    

    public void getPalabrasBeta(ArrayList<String> cadenas, ArrayList<Integer> cont) {
        StringBuilder cadena = new StringBuilder();
        getPalabrasBeta(cadenas,cont,cadena);
    }
    
    private void getPalabrasBeta(ArrayList<String> cadenas, ArrayList<Integer> cont, StringBuilder cadena){
        if (nodo.EsFinPalabra()) {
            cadenas.add(cadena.substring(0));
            cont.add(nodo.GetProb());
        }
        else {
            if(hijo != null) {
                cadena.append(nodo.GetCaracter());
                hijo.getPalabrasBeta(cadenas,cont,cadena);
            }
            else {
                cadena.append(nodo.GetCaracter());
            }
            if ((cadena.length()-1) >= 0) cadena.deleteCharAt(cadena.length()-1);
            if (hermano != null) {
                hermano.getPalabrasBeta(cadenas,cont,cadena);
            }
        }
    }
    
    /**
     * Muestra por pantalla las palabras del trie. Si el trie esta vacio lanza una excepcion.
     * @throws ExcepcionVacio
     */
    public void imprimir() {//throws ExcepcionVacio {
        StringBuilder cadena = new StringBuilder(); // Cadena que cambia de tamaño
       // if (TrieVacio()) throw new ExcepcionVacio("El diccionario esta vacio");
        MostrarPalabra(cadena);
    }
    
    /**
     * Muestra por pantalla las palabras del trie.
     * @param cadena - String
     */
    private void MostrarPalabra(StringBuilder cadena){
        if (nodo.EsFinPalabra()) System.out.println(cadena);
        else {
            if(hijo != null) {
                cadena.append(nodo.GetCaracter());
                hijo.MostrarPalabra(cadena);
            }
            cadena.deleteCharAt(cadena.length()-1);
            if (hermano != null) {
                hermano.MostrarPalabra(cadena);
            }
        }
    }


    /**
     * Elimina el trie.
     */
    public void borrar() {
        hijo = null;
        hermano = null;
        nodo.SetZero();
        altura = 0;
    }
}